#include <bit/stdc++.h>

using namespace std;

// 从树中删除边的最小分数
// 存在一棵无向连通树，树中有编号从0到n-1的n个节点，以及n-1条边
// 给你一个下标从0开始的整数数组nums长度为n，其中nums[i]表示第i个节点的值
// 另给你一个二维整数数组edges长度为n-1
// 其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边
// 删除树中两条不同的边以形成三个连通组件，对于一种删除边方案，定义如下步骤以计算其分数：
// 分别获取三个组件每个组件中所有节点值的异或值
// 最大 异或值和 最小 异或值的 差值 就是这种删除边方案的分数
// 返回可能的最小分数
// 测试链接 : https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/

class Solution 
{
private:
    static const int MAXN = 1010;
    // 下标为原始节点编号
    int dfn[MAXN];
    // 下标为dfn序号
    int eor[MAXN];
    // 下标为dfn序号
    int sz[MAXN];
    int dfnCnt;

    // 当前来到原始编号u，遍历u的整棵树
    void f(vector<int>& nums, vector<vector<int>>& g, int u)
    {
        int i = ++dfnCnt;
        dfn[u] = i;
        sz[i] = 1;
        eor[i] = nums[u];
        for(int v : g[u])
        {
            // dfn 序号为 0，则表示这个节点还没有遍历过
            if(dfn[v] == 0)
            {
                f(nums, g, v);
                sz[i] += sz[dfn[v]];
                eor[i] ^= eor[dfn[v]];
            }
        }
    }

public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) 
    {
        int n = nums.size();
        vector<vector<int>> g(n);
        for(auto& e : edges)
        {
            g[e[0]].emplace_back(e[1]);
            g[e[1]].emplace_back(e[0]);
        }
        fill(dfn, dfn + n, 0);
        dfnCnt = 0;
        f(nums, g, 0);

        int ans = INT_MAX, m = edges.size();
        for(int i = 0, a, b, pre, pos, sum1, sum2, sum3; i < m; ++i)
        {
            a = max(dfn[edges[i][0]], dfn[edges[i][1]]);
            for(int j = i + 1; j < m; ++j)
            {
                b = max(dfn[edges[j][0]], dfn[edges[j][1]]);
                if(a < b)
                {
                    pre = a;
                    pos = b;
                }
                else
                {
                    pre = b;
                    pos = a;
                }
                sum1 = eor[pos];
				// eor[1] : 整棵树的异或和
				// 因为头节点是0，一定拥有最小的dfn序号1
				// f函数调用的时候，也是从0节点开始的
                if(pos < pre + sz[pre])
                {
                    sum2 = eor[pre] ^ eor[pos];
                    sum3 = eor[1] ^ eor[pre];
                }
                else
                {
                    sum2 = eor[pre];
                    sum3 = eor[1] ^ eor[pre] ^ eor[pos];
                }
                ans = min(ans, max(max(sum1, sum2), sum3) - min(min(sum1, sum2), sum3));
            }
        }

        return ans;
    }
};